package com.desheng.bigdata.ds.search;


import com.desheng.bigdata.ds.sort.MySort;

import java.util.Arrays;

/**
 * 二分查找
 *  给我们一个key，和一个数组，查找key在该数组中的index，不在的话，返回该key应该在的位置
 */
public class MyBinarySearch {
    public static void main(String[] args) {
        int arr[] = {10, 9, -2, 6, 7, 1, 3, 8, 0};
        Integer array[] = {10, 9, -2, 6, 7, 1, 3, 8, 0};

        System.out.println("排序前的数组arr：" + Arrays.toString(arr));
        System.out.println("排序前的数组array：" + Arrays.toString(array));
        MySort.insertSort(arr);
        MySort.insertSort(array);
        System.out.println("排序后的数组arr：" + Arrays.toString(arr));
        System.out.println("排序后的数组array：" + Arrays.toString(array));
        int key = 6;
        System.out.println("非递归-->binarySearch(arr, key): " + binarySearch(arr, key));
        System.out.println("递归-->binarySearch(arr, key): " + binarySearch(arr, key, 0, arr.length - 1));
        System.out.println("通用非递归-->binarySearch(arr, key): " + binarySearch(array, key));
        key = 5;
        System.out.println("非递归-->binarySearch(arr, key): " + binarySearch(arr, key));
        System.out.println("递归-->binarySearch(arr, key): " + binarySearch(arr, key, 0, arr.length - 1));
        System.out.println("通用非递归-->binarySearch(arr, key): " + binarySearch(array, key));

    }

    /**
     * 二分查找(递归方式) 必须要有终止
     * @param arr
     * @param key
     * @return
     */
    public static int binarySearch(int arr[], int key, int start, int end) {
        while (start < end) {
            int mid = (start + end) / 2;
            if(key > arr[mid]) {//key在有半部分
                return binarySearch(arr, key, mid + 1, end);
            } else if(key < arr[mid]) {//key在左半部分
                return binarySearch(arr, key, start, mid - 1);
            } else {
                return mid;
            }
        }
        return -(start + 1);
    }

    /**
     * 二分查找(非递归方式)
     * @param arr
     * @param key
     * @return
     */
    public static int binarySearch(int arr[], int key) {
        int start = 0;
        int end = arr.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if(key > arr[mid]) {//key在有半部分
                start = mid + 1;
            } else if(key < arr[mid]) {//key在左半部分
                end = mid - 1;
            } else {
                return mid;
            }
        }
        //到这里的话说明
        return -(start + 1);
    }

    public static <T extends Comparable<T>> int binarySearch(T arr[], T key) {
        int start = 0;
        int end = arr.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if(key.compareTo(arr[mid]) > 0) {//key在有半部分
                start = mid + 1;
            } else if(key.compareTo(arr[mid]) < 0) {//key在左半部分
                end = mid - 1;
            } else {
                return mid;
            }
        }
        //到这里的话说明
        return -(start + 1);
    }

}
